package com.wangc.algorithm.binarysearch;

/**
 * @author wangC
 * @create 2020-07-13 下午10:19
 * @Description  二分法查找数存在 / 有序数组
 **/
public class BSExist {

    public static boolean exist(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return false;
        }

        int L = 0;
        int R = arr.length-1 ;
        int mid = 0 ;
        //L ... R
        while (L < R) {
            // mid =  (L+R)/2
            // L 10e  R 20e 下标太大的情况,或者L+R 存在下标越界的可能
            // mid = L + (R-L)/2
            // mid = L + (R-L)>>1
            mid = L + ((R - L )>>1); // mid = (L+R)/2
            if (arr[mid] == num) {
                return true;
            } else if (arr[mid] > num) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return arr[L] == num;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 8, 11, 17, 19, 35};
        boolean a = exist(arr, 18);
    }


    public boolean bsExistTest(int[] arr, int num) {
        int L = 0 ;
        int R = arr.length - 1;
        int min = 0;
        while (L < R) {
            min = L + ((R - L) >> 2);
            if (arr[min] == num) {
                return true;
            } else if (arr[min] > num) {
                R = min - 1;
            } else {
                L = min + 1;
            }
        }
        return arr[L] == num;
    }


    boolean bsExistTest11(int[] arr, int num) {
        int L = 0;
        int R = arr.length - 1;
        int middle = 0;
        while (L < R) {
            middle = L + (R - L) >> 2;
            if (arr[middle] == num) {
                return true;
            } else if (arr[middle] > num) {
                R = middle - 1;
            } else {
                L = middle + 1;
            }
        }
        return arr[L] == num;
    }
    //arr 为有序数组
    public boolean bsExist(int[] arr, int value) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        int L = 0;
        int R = arr.length - 1;
        int mid = 0;
        while (L < R) {
            mid = L + ((R - L) >> 1);
            if (arr[mid] == value) {
                return true;
            } else if (arr[mid] > value) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return arr[L] == value; //最后一步判断L位置的值
    }

    public boolean bsExistTreste1(int[] arr, int value) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        int L = 0;
        int R = arr.length - 1;
        int mid = 0;
        while (L < R) {
            mid = L + ((R - L) >> 1);
            if (arr[mid] == value) {
                return true;
            } else if (arr[mid] > value) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return arr[L] == value;
    }

    public boolean bsExistTest22(int[] arr, int value) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        int L = 0;
        int R = arr.length - 1;
        int mid = 0;
        while (L < R) {
            mid = L - (R - L) >> 1;
            if (arr[mid] == value) {
                return true;
            } else if (arr[mid] > value) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }

        }
        return arr[L] == value;
    }

    public boolean bsExistTest44(int[] arr, int value) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        int L = 0;
        int R = arr.length - 1;
        int mid = 0;
        while (L < R) {
            mid = L + (R - L) >> 1;
            if (arr[mid] == value) {
                return true;
            } else if (arr[mid] > value) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return arr[L] == value;
    }

}

